1. Field of the Invention
This invention relates generally to the processing of arrays of information, and more particularly, to systematic searches involving selected locations in arrays of information. The invention is particularly relevant to Algebraic Code Excited Linear Prediction (ACELP) speech encoding techniques.
2. Description of the Related Art
In certain applications, arrays of information are searched in a systematic manner. While the search may be systematic, the search can involve skipping one or a plurality of array locations. Furthermore, the search, when conducted for a multi-dimensional array, can involve locations on selected rows, columns, and/or diagonals of the array.
An important application of a systematic array search involves signal encoding. According to one technique for the signal encoding, the signal is sampled in the time domain. The samples are grouped and processed as vectors. These vectors are compared with a preselected collection of vectors referred to as a codebook. When a codebook vector is found that corresponds in a predetermined manner to the input vector, the vector is stored at the array a location index (i.e. address) provides a representation of the corresponding vector sample. In order to reconstruct the original signal, the array index is used to access the location in an array, the accessed array being similar to the original signal. The vector parameter is retrieved from the accessed location in the array and used to represent the sample vector for that particular portion of the original signal from which the vector sample was derived. In this manner, the original signal can be reconstructed with a deviation from the original signal determined by the granularity of the vector values in the array and on the frequency of the sampling process.
Referring to FIG. 1, a block diagram of a processing system for encoding and reconstructing a signal is shown. The original signal is sampled and the resulting sample vectors are applied to processing unit 5. Processing unit 5 searches array 6 and determines which array location stores a vector value that most closely approximates the sample vector. (As will be clear to those skilled in the art of speech processing, array 6 and array 8 exist as concepts for purposes of description and have no physical counterpart.) The index (address) of the array location is then stored if storage of the original signal is desired, or is transmitted to a receiver unit if transmission of the original signal is desired. The processing unit 7 (which may be the same as processing unit 5 for signal storage and retrieval) has the array indices applied thereto. Processing unit 7 retrieves the vector parameter from array 8, array 8 being identical to array 6. The series of vector parameters is applied to the output terminal of processing unit 7, the series of vector parameters reconstructing the series of vector samples applied to the input terminals of processing unit 5. It will be clear that if the original is an analog signal, then the vector samples are digitized prior to application to processing unit 5. Similarly, the series of output vector parameters must be processed to provide an analog reconstruction of the original signal.
As indicated above, the ability of the processing system to reconstruct accurately the original signal generally relates to the granularity of the array, i.e., the size of the array. The larger the number of vector parameters in the array or codebook, the closer the vector parameters can approximate the vector sample. In addition, the original signal can be as rapidly varying and non-periodic as a function of time. These characteristics require a frequent sampling rate for accurate reproduction of the original signal. These two requirements can place enormous computing requirements on the processing units, especially on the processing unit required to perform the encoding process.
Several speech coding standards, such as G.729 and G.723.1, approved by the International Telecommunications Union (ITU), employ a codebook with an algebraic structure. When such a codebook with an algebraic structure is used, the search procedure employs a rectangular matrix to which accesses along diagonals are made. The size of the matrix and the nature of the accesses depend on other system parameters, such as the bit rate of the operation of the encoder and the size of the input vector. The procedure employed by the Enhanced Full Rate Codec (EFRC), presented in the EIA/TIA Interim Standard 641, Revision A, is selected hereinafter to illustrate features of the present invention. The procedure employed by the EFRC provides for accessing the matrix along either diagonal paths or along row paths. In either type of access, a plurality of sequential accesses is made, each access having a starting index (matrix address) and subsequently skipping 5 locations before accessing the next array location in the index.
Digital signal processors are a specialized group of data processing units that provide high computation rates, the high computation rates being at least partially the result of a limited instruction set. The digital signal processor, because of its high computational capabilities, has been applied to the problems of using the ACELP codebook to encode speech signals. Referring to FIG. 2, the use of a digital signal processor 21 for the processing of speech signals is shown. The digital signal processor has coupled thereto an X memory system 23 and a Y memory system 22 for storing signal parameters. One of the memory systems, the X memory system 23, can include a conventional memory unit 231. A portion of the memory locations 2311 in the conventional memory unit 231 store the signal groups representing the array vector parameters. The digital signal processor 21 has applied thereto input vector samples (i.e., representing sampled original speech signal). The input vector samples are then processed and relevant correlation values are computed and stored in the array portion 2311 of the conventional memory 231 according to the procedures of the search technique (i.e., EFRC) used in the current application. The X-memory system portion 2311 is a conventional memory representation of the matrix required to evaluate codebook vectors for an ACELP search. When the closest match between the input vector and a codebook vector is found, the index of that codebook vector is stored. In this manner, a series of memory location addresses are generated that can be used in the reconstruction of the original speech signal.
The processing technique, described above, has several problems in the physical implementation. For example, the correlation values that are used for evaluating codebook vectors are organized as a two-dimensional matrix. When evaluating codebook vectors, it is necessary to access the matrix of correlation values both along diagonals and along rows. Along either the diagonals or along the rows, the accesses, though regularly spaced, are not to neighboring locations. By way of specific example, the EFRC procedure that is being used as example, can skip five positions between sequential accesses. In addition, the matrix used in the ACELP search procedure includes redundant information, i.e., the array has mirror symmetry with respect to the main diagonal of the array. Typically, the redundant groups (i.e., correlation values) are retained to simplify the addressing requirements of the encoding search algorithms.
More precisely, the EFRC speech encoder algorithm fills in the matrix by storing data signal groups (i.e., the vector parameters) along the main diagonal 9 (see Appendix 1) and along each of the sub-diagonals of the matrix (see Appendix 2). Once the matrix has the vector parameters stored therein, the matrix is not modified further until the next frame of speech data. The matrix has several parameters that define the relationship of the EFRC encoding procedure to other procedures. The parameter L is the width and length of the matrix. As indicated above, the ACELP matrix involved in the search procedure has the parameters L=40 providing for 40xc3x9740 matrix or 1600 parameters, each parameter represented by a 16-bit word. Another parameter of the ACELP search procedure is the STEP or the increment used in the particular implementation. In the encoding process, a nest of loops is used to access the matrix array. (The software algorithm for referencing the matrix is included as Appendix 3.) The matrix is referenced along the main diagonal, each reference skipping 5 positions from the previous reference. The remaining referencing is along the rows of the matrix, the referencing again skipping five positions from the previous referencing.
As indicated above, the digital signal processor, because of the computation power, is used to implement the speech encoding procedure. References along a row of an array, even skipping five positions at a time, can be performed efficiently by a digital signal processor even with the reduced instruction set. Difficulty arises because the codebook matrix must be in either a conventional X-memory system or in a conventional Y-memory system. The digital signal processor typically has an insufficient number of pointers assigned to each memory system for providing convenient addressing as required by the search algorithm. The computation would be easily performed if the memory unit, in which the codebook has been stored, has at least seven pointers (i.e., one for each access along a row) assigned thereto in the digital signal processor. When the referencing along a diagonal is included, ten pointers would be required for convenient referencing by the digital signal processor using the EFRC search algorithm. The difficulty can be understood as follows. For the digital signal processor to make search references along a diagonal of the codebook array, the processor must compute the address in a general register and then store the computed address into a data pointer (after having saved the previous value). The required number of pointers are not available in the typical digital signal processor.
The symmetry of the matrix can be used to provide a triangular sub-matrix (of 820 words in the case of EFRC procedures). Consequently, the use of the sub-matrix can be used advantageously to conserve memory space. However, the triangular sub-matrix, because of the new geometry, provides even greater addressing signal difficulties for the digital signal processor because the rows are no longer continuous across the array.
A need has been felt for apparatus and an associated technique for efficient accessing of an array occupying a reduced memory space. A need has further been felt for apparatus and an associated technique that would have the feature of providing an efficient addressing of the array occupying a reduced memory space. A need has still further been felt for apparatus and an associated technique having the feature that a digital signal processor can be used to implement regular but non-neighboring accessing of locations along diagonals or rows during the accessing of an array.
The aforementioned and other features are accomplished, according to the present invention, by providing apparatus, hereinafter referred to as a search accelerator unit (SAU), to assist a digital signal processor in the accessing a sequence of regularly (incrementally) spaced non-neighboring locations of an array. The SAU of the present invention, the SAU being external to the digital signal processor, supplements the addressing capability of a digital signal processor so that references to a sequence of entries in the array can be performed more efficiently. In addition, when the (two-dimensional) array is symmetrical, the redundant entries can be eliminated by forming a triangular sub-array. The sub-array achieves a significant reduction in memory required to store the data signal groups. The apparatus and technique of the present invention is described with reference to the ACELP search procedure employed in the EFRC search encoder. Apparatus is disclosed for the SAU that permits the search of a sub-array wherein both the size of the matrix and the incremental step can be programmed.